{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Logical Design\n",
    "\n",
    "## Objective and Prerequisites\n",
    "\n",
    "In this example, you’ll learn how to solve a logical design problem, which involves constructing a circuit using the minimum number of NOR gates (devices with two inputs and  one output) that will perform the logical function specified by a truth table. We’ll show you how to formulate this problem as a binary optimization problem using the Gurobi Python API and then use Gurobi Optimizer to automatically find the optimal solution.\n",
    "\n",
    "This model is example 12 from the fifth edition of Model Building in Mathematical Programming by H. Paul Williams on pages 266-267 and 320-321.\n",
    "\n",
    "This example is at the intermediate level, where we assume that you know Python and the Gurobi Python API and that you have some knowledge of building mathematical optimization models.\n",
    "\n",
    "**Download the Repository** <br /> \n",
    "You can download the repository containing this and other examples by clicking [here](https://github.com/Gurobi/modeling-examples/archive/master.zip). "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem Description\n",
    "\n",
    "Logical circuits have a given number of inputs and one output. Impulses may be applied to the inputs of a given logical circuit, and it will respond by giving either an output (signal 1) or no output (signal 0). The input impulses are of the\n",
    "same kind as the outputs - 1 (positive input) or 0 (no input).\n",
    "\n",
    "In this example, a logical circuit is to be built up of NOR gates. A NOR gate is a device with two inputs and one output. It has the property that there is positive output (signal 1) if and only if neither input is positive, that is, both inputs have the value 0. By connecting such gates together with outputs from one gate possibly being inputs into another gate, it is possible to construct a circuit to perform any desired logical function. For example, the circuit illustrated in the following figure will respond to the inputs A and B in the way indicated by the truth table.\n",
    "![circuit](circuit.PNG)\n",
    "\n",
    "The objective is to construct a circuit using the minimum number of NOR gates that will perform the logical function specified by the following  truth table.\n",
    "\n",
    "| A | B | Output |\n",
    "| --- | --- | --- | \n",
    "| 0 | 0 | 0 |\n",
    "| 0 | 1 | 1 |\n",
    "| 1 | 0 | 1 |\n",
    "| 1 | 1 | 0 |\n",
    "\n",
    "‘Fan-in’ and ‘fan-out’ are not permitted. That is, more than one output from a NOR gate cannot lead into one input nor can one output lead into more than one input. It may be assumed throughout that the optimal design is a ‘subnet’ of the ‘maximal’ net shown in the following figure.\n",
    "![subnet](subnet.PNG)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Model Formulation\n",
    "\n",
    "### Sets and Indices\n",
    "\n",
    "$i \\in \\text{Gates}=\\{1,...,7\\}$\n",
    "\n",
    "$i \\in \\text{G47}=\\{4,...,7\\}$\n",
    "\n",
    "$r \\in \\text{Rows}=\\{1,...,4\\}$\n",
    "\n",
    "### Parameters\n",
    "\n",
    "$\\text{valueA}_{i,r} \\in \\{0,1 \\}$: Value of the external input A in row  $r$ of the truth table for gate $i$.\n",
    "\n",
    "$\\text{valueB}_{i,r} \\in \\{0,1 \\}$: Value of the external input B in row  $r$ of the truth table for gate $i$.\n",
    "\n",
    "### Decision Variables\n",
    "\n",
    "$\\text{NOR}_{i} \\in \\{0,1 \\}$: This binary variable is equal to 1, if NOR gate $i$  is selected, 0 otherwise.\n",
    "\n",
    "$\\text{inputA}_{i} \\in \\{0,1 \\}$: This binary variable is equal to 1, if external input A is an input to NOR gate $i$ , and 0 otherwise.\n",
    "\n",
    "$\\text{inputB}_{i} \\in \\{0,1 \\}$: This binary variable is equal to 1, if external input B is an input to NOR gate $i$ , and 0 otherwise.\n",
    "\n",
    "$\\text{output}_{i,r} \\in \\{0,1 \\}$: This binary variable is the output from gate $i$ for the combination of external input signals specified  in row $r$  of the truth table.\n",
    "\n",
    "### Constraints\n",
    "\n",
    "**External input**: A NOR gate can only have an external input if it exists.\n",
    "\n",
    "\\begin{equation}\n",
    "\\text{NOR}_{i} \\geq \\text{inputA}_{i}  \\quad \\forall i \\in \\text{Gates}\n",
    "\\end{equation}\n",
    "\n",
    "\\begin{equation}\n",
    "\\text{NOR}_{i} \\geq \\text{inputB}_{i}  \\quad \\forall i \\in \\text{Gates}\n",
    "\\end{equation}\n",
    "\n",
    "**NOR gates**:If a NOR gate has one (or two) external inputs leading into it, only one (or no) NOR gates can feed into it. \n",
    "\n",
    "\\begin{equation}\n",
    "\\text{NOR}_{2} + \\text{NOR}_{3} + \\text{inputA}_{1} + \\text{inputB}_{1} \\leq 2\n",
    "\\end{equation}\n",
    "\n",
    "\\begin{equation}\n",
    "\\text{NOR}_{4} + \\text{NOR}_{5} + \\text{inputA}_{2} + \\text{inputB}_{2} \\leq 2\n",
    "\\end{equation}\n",
    "\n",
    "\\begin{equation}\n",
    "\\text{NOR}_{6} + \\text{NOR}_{7} + \\text{inputA}_{3} + \\text{inputB}_{3} \\leq 2\n",
    "\\end{equation}\n",
    "\n",
    "These constraints are based on the circuit shown in the figure of the ‘maximal’ net. \n",
    "\n",
    "**Output signals**: The output signal from NOR gate $i$ must be the correct logical function (NOR) of the input signals into gate $i$, if gate $i$ exists. \n",
    "\n",
    "\\begin{equation}\n",
    "\\text{output}_{2,r} + \\text{output}_{1,r} \\leq 1 \\quad \\forall r \\in \\text{Rows}\n",
    "\\end{equation}\n",
    "\n",
    "\\begin{equation}\n",
    "\\text{output}_{3,r} + \\text{output}_{1,r} \\leq 1 \\quad \\forall r \\in \\text{Rows}\n",
    "\\end{equation}\n",
    "\n",
    "\\begin{equation}\n",
    "\\text{valueA}_{i,r}*\\text{inputA}_{i} + \\text{output}_{i,r} \\leq 1 \\quad \\forall i \\in \\text{Gates}, r \\in \\text{Rows}\n",
    "\\end{equation}\n",
    "\n",
    "\\begin{equation}\n",
    "\\text{valueB}_{i,r}*\\text{inputB}_{i} + \\text{output}_{i,r} \\leq 1 \\quad \\forall i \\in \\text{Gates}, r \\in \\text{Rows}\n",
    "\\end{equation}\n",
    "\n",
    "\\begin{equation}\n",
    "\\text{valueA}_{i,r}*\\text{inputA}_{i} + \\text{valueB}_{i,r}*\\text{inputB}_{i} + \n",
    "\\text{output}_{i,r} - \\text{NOR}_{i}  \\geq 0 \\quad \\forall i \\in \\text{G47}, r \\in \\text{Rows}\n",
    "\\end{equation}\n",
    "\n",
    "\\begin{equation}\n",
    "\\text{valueA}_{1,r}*\\text{inputA}_{1} + \\text{valueB}_{1,r}*\\text{inputB}_{1} + \n",
    "\\text{output}_{2,r} + \\text{output}_{3,r} + \\text{output}_{1,r} - \\text{NOR}_{1}  \\geq 0 \n",
    "\\quad \\forall r \\in \\text{Rows}\n",
    "\\end{equation}\n",
    "\n",
    "\\begin{equation}\n",
    "\\text{valueA}_{2,r}*\\text{inputA}_{2} + \\text{valueB}_{2,r}*\\text{inputB}_{2} + \n",
    "\\text{output}_{4,r} + \\text{output}_{5,r} + \\text{output}_{2,r} - \\text{NOR}_{2}  \\geq 0 \n",
    "\\quad \\forall r \\in \\text{Rows}\n",
    "\\end{equation}\n",
    "\n",
    "\\begin{equation}\n",
    "\\text{valueA}_{3,r}*\\text{inputA}_{3} + \\text{valueB}_{3,r}*\\text{inputB}_{3} + \n",
    "\\text{output}_{6,r} + \\text{output}_{7,r} + \\text{output}_{3,r} - \\text{NOR}_{3}  \\geq 0 \n",
    "\\quad \\forall r \\in \\text{Rows}\n",
    "\\end{equation}\n",
    "\n",
    "**Gate 1**: For NOR gate 1, the output variables are fixed at the values specified in the truth table. \n",
    "\n",
    "\\begin{equation}\n",
    "\\text{output}_{1,1} = 0, \\text{output}_{1,2} = 1, \\text{output}_{1,3} = 1,  \\text{output}_{1,4} = 0   \n",
    "\\end{equation}\n",
    "\n",
    "To avoid a trivial solution containing no NOR gates, it is necessary to impose a constraint that selects NOR gate 1.\n",
    "\n",
    "\\begin{equation}\n",
    "\\text{NOR}_{1} \\geq 1  \n",
    "\\end{equation}\n",
    "\n",
    "**Gates and output**: If there is an output signal of 1 from a particular NOR gate for any combination of the input signals, then that gate must exist.\n",
    "\n",
    "\\begin{equation}\n",
    "\\text{NOR}_{i} - \\text{output}_{i,r} \\geq 0 \\quad \\forall i \\in \\text{Gates}, r \\in \\text{Rows}\n",
    "\\end{equation}\n",
    "\n",
    "### Objective Function\n",
    "\n",
    "**Number of gates**: The objective is to minimize the number of NOR gates selected.\n",
    "\n",
    "\\begin{equation}\n",
    "\\text{Minimize} \\quad  \\sum_{i \\in \\text{Gates}} \\text{NOR}_{i}\n",
    "\\end{equation}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Python Implementation\n",
    "\n",
    "We import the Gurobi Python Module."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%pip install gurobipy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import gurobipy as gp\n",
    "from gurobipy import GRB\n",
    "\n",
    "# tested with Python 3.11 & Gurobi 11.0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Input data\n",
    "\n",
    "We define all the input data for the model."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# List of NOR gates 1 to 7.\n",
    "\n",
    "gates = ['1','2','3','4','5','6','7']\n",
    "\n",
    "# List of NOR gates 4 to 7.\n",
    "\n",
    "gates47 = ['4','5','6','7']\n",
    "\n",
    "# List of rows of the truth-table in the range 1 to 4.\n",
    "\n",
    "rows = ['1','2','3','4']\n",
    "\n",
    "# Create a dictionary to capture the value of the external input A and B in the r row of the truth table, for each \n",
    "# NOR gate i.\n",
    "\n",
    "gatesRows, valueA, valueB = gp.multidict({\n",
    "    ('1','1'): [0,0],\n",
    "    ('1','2'): [0,1],\n",
    "    ('1','3'): [1,0],\n",
    "    ('1','4'): [1,1],\n",
    "    ('2','1'): [0,0],\n",
    "    ('2','2'): [0,1],\n",
    "    ('2','3'): [1,0],\n",
    "    ('2','4'): [1,1],\n",
    "    ('3','1'): [0,0],\n",
    "    ('3','2'): [0,1],\n",
    "    ('3','3'): [1,0],\n",
    "    ('3','4'): [1,1],\n",
    "    ('4','1'): [0,0],\n",
    "    ('4','2'): [0,1],\n",
    "    ('4','3'): [1,0],\n",
    "    ('4','4'): [1,1],\n",
    "    ('5','1'): [0,0],\n",
    "    ('5','2'): [0,1],\n",
    "    ('5','3'): [1,0],\n",
    "    ('5','4'): [1,1],\n",
    "    ('6','1'): [0,0],\n",
    "    ('6','2'): [0,1],\n",
    "    ('6','3'): [1,0],\n",
    "    ('6','4'): [1,1],\n",
    "    ('7','1'): [0,0],\n",
    "    ('7','2'): [0,1],\n",
    "    ('7','3'): [1,0],\n",
    "    ('7','4'): [1,1]\n",
    "})\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Model Deployment\n",
    "\n",
    "We create a model and the variables. The main decision is to determine the $\\text{NOR}_{i}$ variables that selects the NOR gates to consider in the logical circuit. The rest of the variables ensure that the circuit generates the output of the truth table."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Using license file c:\\gurobi\\gurobi.lic\n"
     ]
    }
   ],
   "source": [
    "model = gp.Model('logicalDesign')\n",
    "\n",
    "# Decision variables to select NOR gate i.\n",
    "NOR = model.addVars(gates, vtype=GRB.BINARY, name=\"NORgate\" )\n",
    "\n",
    "# In order to avoid a trivial solution containing no NOR gates, it is necessary to impose a constraint \n",
    "# that selects NOR gate 1.\n",
    "\n",
    "NOR['1'].lb = 1\n",
    "\n",
    "# Variables to decide if external input A is an input to NOR gate i.\n",
    "inputA = model.addVars(gates, vtype=GRB.BINARY, name=\"inputA\")\n",
    "\n",
    "# Variables to decide if external input B is an input to NOR gate i.\n",
    "inputB = model.addVars(gates, vtype=GRB.BINARY, name=\"inputB\")\n",
    "\n",
    "# Output decision variables.\n",
    "output = model.addVars(gatesRows, vtype=GRB.BINARY, name=\"output\")\n",
    "\n",
    "# For NOR gate 1, the output variables are fixed at the values specified in the truth table.\n",
    "\n",
    "output['1','1'].ub = 0\n",
    "output['1','2'].lb = 1\n",
    "output['1','3'].lb = 1\n",
    "output['1','4'].ub = 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A NOR gate can only have an external input if it exists."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# External inputs constraints\n",
    "\n",
    "externalInputsA = model.addConstrs( ( NOR[i] >= inputA[i]  for i in gates), name='externalInputsA')\n",
    "\n",
    "externalInputsB = model.addConstrs( ( NOR[i] >= inputB[i]  for i in gates), name='externalInputsB')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If a NOR gate has one (or two) external inputs leading into it, only one (or no) NOR gates can feed into it. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "# NOR gates constraints\n",
    "\n",
    "NORgate1 = model.addConstr(NOR['2'] + NOR['3'] + inputA['1'] + inputB['1'] <= 2, name='NORgate1')\n",
    "\n",
    "NORgate2 = model.addConstr(NOR['4'] + NOR['5'] + inputA['2'] + inputB['2'] <= 2, name='NORgate2')\n",
    "\n",
    "NORgate3 = model.addConstr(NOR['6'] + NOR['7'] + inputA['3'] + inputB['3'] <= 2, name='NORgate3')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The output signal from NOR gate i must be the correct logical function (NOR) of the input signals into gate i, if gate i exists."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Output signal constraint.\n",
    "\n",
    "outputSignals1_1 = model.addConstrs( (output['2',r] + output['1',r] <= 1 for r in rows), name='outputSignals1_1' )\n",
    "\n",
    "outputSignals1_2 = model.addConstrs( (output['3',r] + output['1',r] <= 1 for r in rows), name='outputSignals1_2' )\n",
    "\n",
    "outputSignals2_1 = model.addConstrs( (output['4',r] + output['2',r] <= 1 for r in rows), name='outputSignals2_1' )\n",
    "\n",
    "outputSignals2_2 = model.addConstrs( (output['5',r] + output['2',r] <= 1 for r in rows), name='outputSignals2_2' )\n",
    "\n",
    "outputSignals3_1 = model.addConstrs( (output['6',r] + output['3',r] <= 1 for r in rows), name='outputSignals3_1' )\n",
    "\n",
    "outputSignals3_2 = model.addConstrs( (output['7',r] + output['3',r] <= 1 for r in rows), name='outputSignals3_2' )\n",
    "\n",
    "\n",
    "outputSignals4 = model.addConstrs( (valueA[i,r]*inputA[i] + output[i,r] <= 1 for i,r in gatesRows), name='outputSignals4')\n",
    "\n",
    "outputSignals5 = model.addConstrs( (valueB[i,r]*inputB[i] + output[i,r] <= 1 for i,r in gatesRows), name='outputSignals5')\n",
    "\n",
    "outputSignals6 = model.addConstrs( (valueA[i,r]*inputA[i] + valueB[i,r]*inputB[i] + output[i,r] - NOR[i] >= 0 \n",
    "                                    for i,r in gatesRows if i in gates47), name='outputSignals6')\n",
    "\n",
    "outputSignals7 = model.addConstrs( (valueA['1',r]*inputA['1'] + valueB['1',r]*inputB['1'] \n",
    "                                    + output['2',r] + output['3',r] + output['1',r] - NOR['1'] >= 0\n",
    "                                    for i,r in gatesRows), name='outputSignals7')\n",
    "\n",
    "outputSignals8 = model.addConstrs( (valueA['2',r]*inputA['2'] + valueB['2',r]*inputB['2'] \n",
    "                                    + output['4',r] + output['5',r] + output['2',r] - NOR['2'] >= 0\n",
    "                                    for i,r in gatesRows), name='outputSignals8')\n",
    "\n",
    "outputSignals9 = model.addConstrs( (valueA['3',r]*inputA['3'] + valueB['3',r]*inputB['3'] \n",
    "                                    + output['6',r] + output['7',r] + output['3',r] - NOR['3'] >= 0\n",
    "                                    for i,r in gatesRows), name='outputSignals9')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If there is an output signal of 1 from a particular NOR gate for any combination of the input signals, then that gate must exist."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Gate and output signals constraints\n",
    "\n",
    "gateOutput = model.addConstrs( (NOR[i] - output[i,r] >= 0 for i,r in gatesRows) , name='gateOutput')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The objective is to minimize the number of NOR gates selected."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Objective function.\n",
    "\n",
    "model.setObjective(NOR.sum(), GRB.MINIMIZE)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Gurobi Optimizer version 9.1.0 build v9.1.0rc0 (win64)\n",
      "Thread count: 4 physical cores, 8 logical processors, using up to 8 threads\n",
      "Optimize a model with 225 rows, 49 columns and 696 nonzeros\n",
      "Model fingerprint: 0x9adba516\n",
      "Variable types: 0 continuous, 49 integer (49 binary)\n",
      "Coefficient statistics:\n",
      "  Matrix range     [1e+00, 1e+00]\n",
      "  Objective range  [1e+00, 1e+00]\n",
      "  Bounds range     [1e+00, 1e+00]\n",
      "  RHS range        [1e+00, 2e+00]\n",
      "Presolve removed 225 rows and 49 columns\n",
      "Presolve time: 0.00s\n",
      "Presolve: All rows and columns removed\n",
      "\n",
      "Explored 0 nodes (0 simplex iterations) in 0.01 seconds\n",
      "Thread count was 1 (of 8 available processors)\n",
      "\n",
      "Solution count 1: 5 \n",
      "\n",
      "Optimal solution found (tolerance 1.00e-04)\n",
      "Best objective 5.000000000000e+00, best bound 5.000000000000e+00, gap 0.0000%\n"
     ]
    }
   ],
   "source": [
    "# Verify model formulation\n",
    "\n",
    "model.write('logicalDesign.lp')\n",
    "\n",
    "# Run optimization engine\n",
    "\n",
    "model.optimize()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "\n",
      "_________________________________________________________________________________\n",
      "The optimal circuit design:\n",
      "_________________________________________________________________________________\n",
      "NOR gate 1 is active.\n",
      "NOR gate 2 is active, with external inputs A and B values of 1.0 and  1.0.\n",
      "NOR gate 3 is active.\n",
      "NOR gate 6 is active, with external inputs A and B values of 0.0 and  1.0.\n",
      "NOR gate 7 is active, with external inputs A and B values of 1.0 and  0.0.\n"
     ]
    }
   ],
   "source": [
    "# Output reports\n",
    "\n",
    "print(\"\\n\\n_________________________________________________________________________________\")\n",
    "print(f\"The optimal circuit design:\")\n",
    "print(\"_________________________________________________________________________________\")\n",
    "for i in gates:\n",
    "    if (NOR[i].x > 0.5):\n",
    "        if (inputA[i].x + inputB[i].x > 0.5):\n",
    "            print(f\"NOR gate {i} is active, with external inputs A and B values of {inputA[i].x} and  {inputB[i].x}.\")\n",
    "        else:\n",
    "            print(f\"NOR gate {i} is active.\")\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## References\n",
    "\n",
    "H. Paul Williams, Model Building in Mathematical Programming, fifth edition.\n",
    "\n",
    "Copyright © 2020 Gurobi Optimization, LLC"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
